#Secure Channels Problem Set 4 Task 5
#Jiaqi Weng 115131
#Vasilii Ponteleev 115151
#Naveeni Kumar Goswam 113967

#Compile it with python 3.4.*


class Polynomial:

    def __init__(self, hexValue):
        if hexValue < 0:
            raise ValueError("The value represented polinomial should be not negative")
        self.hexValue = hexValue

    def asBitListFrom0Bit(self):
        res = []
        tmp = self.hexValue
        while tmp != 0:
            res.append(tmp & 1)
            tmp >>= 1
        return res

    def degree(self):
        degree = 0
        tmp = self.hexValue
        while tmp != 0:
            degree += 1
            tmp >>= 1
        return degree - 1        

    def __str__(self):
        power = 0
        stringRep = []
        for bit in self.asBitListFrom0Bit():
            if bit == 1:
               stringRep.append("x^" + str(power))
            power += 1   
        if not stringRep:
            return "0"
        else:
            return " + ".join(stringRep[::-1])

    def __eq__(self, other):
        return self.hexValue == other.hexValue

    def __neq__(self, other):
        return self.hexValue != other.hexValue

    

class FiniteField:

    def __init__(self, degree, polynomial):
        self.polynomial = polynomial
        self.degree = degree

    def __str__(self):
        return "GF(2^" + self.degree + ") field defined by " + self.polynomial
    
    def add(self, polyA, polyB):
        self.__checkDegreesOrPanic(polyA, polyB)
        return Polynomial(polyA.hexValue ^ polyB.hexValue)

    def mult(self, polyA, polyB):
        self.__checkDegreesOrPanic(polyA, polyB)
        res = 0;
        a = polyA.hexValue
        b = polyB.hexValue
        for i in range(0, self.degree):
           if b & 1 != 0:
                res ^= a
           a <<= 1
           #if a degree of the result is greater than field degree
           if a & (1 << self.degree) != 0:
               #substruct field polynomial to diminish degree
                a ^= self.polynomial.hexValue
           b >>= 1
        return Polynomial(res)

    def substruct(self, polyA, polyB):
        self.__checkDegreesOrPanic(polyA, polyB)
        return self.add(polyA, polyB)

    def inverse(self, polyA):
        self.__checkDegreeOrPanic(polyA)
        #For GF(2^p) holds: a^-1 = a^(p - 2) mod p
        return self.__powerOf(polyA, (1 << self.degree) - 2)
    
    def divide(self, polyA, polyB):
        self.__checkDegreesOrPanic(polyA, polyB)
        return self.mult(polyA, self.inverse(polyB))

    def __checkDegreesOrPanic(self, polyA, polyB):
        if polyA.degree() >= self.degree or polyB.degree() >= self.degree:
            raise ValueError("Arguments degree has exceeded field limit")

    def __checkDegreeOrPanic(self, polyA):
        if polyA.degree() >= self.degree:
            raise ValueError("Argument degree has exceeded field limit")

    def __powerOf(self, polyX, n):
        if n == 0:
            return Polynomial(0x01)
        else:
            if n == 1:
                return polyX
            else:
                if n & 1 == 0:
                    return self.__powerOf(self.mult(polyX, polyX), n >> 1)
                else:
                    if n & 1 != 0:
                        return self.mult(polyX, self.__powerOf(self.mult(polyX, polyX), (n - 1) >> 1))


class FiniteFieldBuilder:
        
    def ofDegree(self, degree):
        self.degree = degree
        return self

    def usingIrreduciblePolynomial(self, polynomial):
        self.polynomial = polynomial
        return self

    def build(self):
        if self.degree <= 0:
           raise ValueError("GF degree should be positive")
        if not isinstance(self.polynomial, Polynomial):
           raise ValueError("GF should be initialized with Polynomial object")
        return FiniteField(self.degree, self.polynomial)
        
